package 力扣._00周赛._427周赛.问题3;

class Solution2 {
    public long maxSubarraySum(int[] nums, int k) {
        long sum = 0;
        long max = Long.MIN_VALUE;

        // 前缀和计算
        long[] preSum = new long[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        // 初始化当前最大和
        int window = k;

        while (window <= nums.length) {
            long currentMax = Long.MIN_VALUE;
            // 是否有正数
            boolean hasPositive = false;

            // 计算当前窗口和
            for (int i = window - 1; i < nums.length; i++) {
                sum = preSum[i + 1] - preSum[i + 1 - window];
                if (sum > 0) {
                    hasPositive = true;
                }
                currentMax = Math.max(currentMax, sum);
            }

            // 更新全局最大值
            max = Math.max(max, currentMax);
            if (!hasPositive) {
                break;
            }

            // 增加窗口大小
            window += k;
        }

        return max;
    }

    public static void main(String[] args) {
        // 测试用例

    }

}